/**
 * 给定一个从1 到 n 排序的整数列表。
 * 首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
 * 第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
 * 我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
 * 返回长度为 n 的列表中，最后剩下的数字。
 * <p>
 * 示例：
 * <p>
 * 输入:
 * n = 9,
 * 1 2 3 4 5 6 7 8 9
 * 2 4 6 8
 * 2 6
 * 6
 * <p>
 * 输出:
 * 6
 */
class Solution {

    public static void main(String[] args) {
        /*for (int i = 1; i < 50; i++) {
            System.out.println(i + "-" + lastRemaining1(i));
        }*/
        for (int i = 1; i < 50; i++) {
            System.out.println(i + "-" + lastRemaining(i));
        }
        // System.out.println(lastRemaining(5));
    }

    public static int lastRemaining(int n) {
        return lastRemaining(n, true);
    }

    public static int lastRemaining(int n, boolean positive) {
        if (n == 1) {
            return 1;
        } else if (n == 3) {
            return 2;
        }
        if (n % 2 == 0 && !positive) {
            return lastRemaining((n + 1) / 2, !positive) * 2 - 1;
        } else {
            return lastRemaining(n / 2, !positive) * 2;
        }
    }


    /**
     * 遍历法
     *
     * @param n
     * @return
     */
    public static int lastRemaining1(int n) {
        if (n <= 2) {
            return n;
        }
        // 除以2做第一次筛选
        n /= 2;
        int[] nums = new int[n];
        // 构建初始数组
        for (int i = 0, t = 2; i < n; i++, t += 2) {
            nums[i] = t;
        }
        if (n == 1) {
            return nums[0];
        }
        // 统计当前剩余格式
        int left = n;
        // 记录遍历顺序
        boolean positive = false;
        // 记录是否要删除
        boolean delete;
        while (true) {
            delete = true;
            if (positive) {
                // 正序
                for (int i = 0; i < n; i++) {
                    if (nums[i] != -1) {
                        if (delete) {
                            nums[i] = -1;
                            delete = false;
                            left--;
                        } else {
                            delete = true;
                        }
                    }
                }
            } else {
                // 倒序
                for (int i = n - 1; i >= 0; i--) {
                    if (nums[i] != -1) {
                        if (delete) {
                            nums[i] = -1;
                            delete = false;
                            left--;
                        } else {
                            delete = true;
                        }
                    }
                }
            }
            positive = !positive;
            if (left == 1) {
                break;
            }
        }
        // 遍历返回
        for (int num : nums) {
            if (num != -1) {
                return num;
            }
        }
        return 0;
    }


}